A message authentication code (MAC, or MAC “tag”) is a digital signal sequence used for authenticating a message exchanged between a sender and receiver each having a shared secret “key.” In a typical MAC authentication scenario, the sender of a message runs it through a cryptographic hash function having the message and the secret key as inputs, yielding a MAC tag as an output. The sender then sends the message and the tag to the receiver. The receiver runs the received message through the same MAC algorithm using the same key, yielding a second MAC tag. The receiver then compares the tag generated by itself to the tag received from the sender and if they are the same, the message is deemed authentic. If they are not the same, it is an indication that the message was altered or compromised in some manner during the exchange.
Although MAC tags are relatively short, they can represent a significant overhead in data networks that include multiple nodes generating multiple messages and hence, multiple different MAC tags. This overhead is most pronounced when the MAC tags are larger than the messages themselves. As one example, distributed sensor networks (such as “Smart Grid” energy metering networks) rely on a multitude of deployed cheap sensors to report measurements, such as temperature, electricity consumption, etc. This data is transmitted hop-by-hop over multiple nodes and needs to be authenticated and verified by a central node. The measurement data can be quite small (e.g., on the order of 10-15 bits), whereas the typical MAC tag is 128 bits which is roughly an order of magnitude larger than the data it authenticates.
To mitigate the overheads inherent in multi-node data networks, the concept of aggregate MACs (comprising an aggregation of multiple MAC tags into a shorter tag) has been proposed by the cryptographic community. Aggregate MACs are much shorter than the concatenation of constituent MACs, thus greatly reducing the network overhead, yet can still be verified by a central node that shares a distinct key with each sending node. However, existing MAC aggregation techniques do not guarantee security of the aggregate MAC if more than two identical messages are aggregated together. This is a significant impediment in the practice of secure networking, since a plurality of message delivery and routing protocols, such as flooding, rely on (or at least allow) duplicate messages being authenticated. Accordingly, there is a need for improved MAC aggregation techniques that not only greatly reduce the overhead of a multi-node data network, but that guarantee security even in the case where constituent MACs may be aggregated in duplicate. Embodiments of the present invention are directed to addressing this need.